package tree;

public class Ex543 {
    //返回二叉树节点最大距离
    /* 
        最大距离的可能：
        某个子树提供的最大距离；
        子树最大高度
    */

    class Solution {
        public int diameterOfBinaryTree(TreeNode root) {
            return postOrder(root)[0];
        }

        //int[2] : 第0位存储子树最大距离，第1位存储子树高度 - 1;
        public int[] postOrder(TreeNode root) {
            if (root == null) return new int[]{0, 0};
            int[] left = postOrder(root.left), right = postOrder(root.right);
            int[] res = new int[2];
            res[1] = Math.max(left[1], right[1]) + 1;
            //当前最大距离在两种可能中选择
            res[0] = Math.max(left[1] + right[1], Math.max(left[0], right[0]));
            return res;
        }
    }

}
